//【案例开放025】0305上机编程“最长空闲内存”学习交流
//【案例开放025】0305上机编程“最长空闲内存”学习交流
//日期：2021-03-12 16:53浏览：15708回复：352026-03-12 失效
// 1.   题目
//今天学习0305工作级第三题、专业级第一题。题目：最长空闲内存
//某系统中有一空间连续的内存，被划分成多个大小相同的内存块。内存的使用状态记录在字符串
// memory 中，每个内存块的状态用字符 x 或 . 表示，其中： ·     .
//表示该内存块空闲； ·     x 表示该内存块被使用，x 为小写字母。 现在可释放其中
//最多 cnt 个内存块（即字符串中的 x 变成 .），以获得一块空间连续的、且 最长的
//空闲内存，请计算并返回该最长空闲内存的内存块数量。 示例 1： 输入： memory =
// "..x..x..xx..." cnt = 2 输出：8 解释： image.png 将 memory[2] 与 memory[5]
//的内存块释放，可获得从 memory[0] 到 memory[7]、长度为 8 的连续空闲内存； 将
// memory[5] 与 memory[8] 的内存块释放，可获得从 memory[3] 到 memory[8]、长度为
// 6 的连续空闲内存； 将 memory[8] 与 memory[9] 的内存块释放，可获得从 memory[6]
//到 memory[12]、长度为 7 的连续空闲内存； 其他释放方式获得的连续空闲内存都小于
// 8； 因此返回 8。 示例 2： 输入：
// memory = "....x."
// cnt = 3
//输出：6
//示例 3：
//输入：
// memory = "xx.x..xx....x..."
// cnt = 0
//输出：4
//提示：0 <= cnt <= memory.length <= 10^5
// 2.   题目分析
//题目理解：
//可释放其中最多 cnt 个内存块（即字符串中的 x 变成
//.）有很多种释放方法，需要找到最长的连续空闲内存。
// cnt可能等于0，这种情况只需要数一下连续的’.’的个数。
// cnt可能用不完（即cnt大于’x’的个数），这种情况直接返回memory的长度。
//暴力解法：
//其中一种暴力解法思路：可以每次将最多cnt个’x’变成’.’，然后数一下最长连续的’.’个数，再将"."还原成"x"。
//暴力解法通常需要两层循环，见员工7的代码。
//注：以下部分总结摘自leetcode1004。
//解题思路：
// l  重点：题意转换
//把“最多可以把 cnt 个 ‘x’ 转换变成 ‘.’，求仅包含 ‘.’
//的最长字符串子数组的长度”的问题，转换为：
//“找出一个最长的子数组，该子数组内最多允许有 cnt 个相邻的‘x’ ”。
//经过上面的题意转换，我们可知本题是求最大连续子区间，可以使用滑动窗口方法。
//滑动窗口的限制条件是：窗口内最多有 cnt 个‘x’。
//主要处理逻辑：
// l  使用 left 和 right 两个指针，分别指向滑动窗口的左右边界。
// l  right 主动右移：right 指针每次移动一步。当 memory[right]
// 为‘x’，说明滑动窗口内增加了一个‘x’； l  left
// 被动右移：判断此时窗口内‘x’的个数，如果超过了 cnt，则 left
// 指针被迫右移，直至窗口内的 ‘x’ 的个数小于等于 cnt 为止。 l
// 滑动窗口长度的最大值就是答案。
// 3.   员工1-C代码：12行、最大圈复杂度5
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

int GetMaxFreeMemoryLen(char *memory, int cnt) {
  int len = strlen(memory);
  int l = 0, r = 0;
  while (r < len) {
    if (memory[r++] == 'x') cnt--;
    if (cnt < 0 && memory[l++] == 'x') cnt++;
  }
  return r - l;
}
//该解法维护一个cnt变量，当字符为’x’时，递减cnt；当cnt<0的时候，左指针右移、递增cnt。
//右指针移动可以表示扩张窗口，左指针移动表示缩小窗口。
//当遇到了太多 ‘x’ 时，资源已不足（cnt < 0），此时就需要缩小窗口了。
//向窗口加入（memory[r++]）或移除（memory[l++]）一个数组元素，可以在O(1)内更新cnt。
//时间复杂度O(N)；代码非常精炼、符合CleanCode要求。
class Solution {
 public:
  int GetMaxFreeMemoryLen(string memory, int cnt) {
    int left = 0;
    int right = 0;
    int fcount = 0;
    int result = 0;
    while (right < memory.size()) {
      fcount += memory[right] == 'x';
      while (fcount > cnt) {
        fcount -= memory[left] == 'x';
        left++;
      }
      result = max(result, right - left + 1);
      right++;
    }
    return result;
  }
};
//该解法把滑动窗口看成一个队列，每次在临界的时候维护队列的左指针left。代码思路：
// l
// 用left和right来记录窗口的长度，fcount记录窗口中’x’的个数，result记录最大长度；
// l  如果memory[right]==’x’，则fcount加1；
// l
// 当fcount>cnt时，窗口就不满足条件了，此时就要移动left来使窗口满足条件，left不断右移直到fcount<=cnt；
// l  更新result，right右移一步。
//时间复杂度O(N)；代码简洁易懂、符合CleanCode要求。
